package structure.link;

import android.app.Activity;
import android.os.Bundle;
import android.support.annotation.Nullable;
import java.util.Arrays;
import suanfa.Sort;

/**
 * 创建时间：2018年01月03日11:06 <br>
 * 作者：fuchaoyang <br>
 * 描述：
 */

public class TestSortActivity extends Activity {

  @Override protected void onCreate(@Nullable Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);

    //Stack<String> stack = new Stack<>();
    //stack.push("001");
    //stack.push("002");
    //stack.push("003");
    //stack.push("004");
    //stack.push("005");
    //stack.display();
    //
    //System.out.println("stack.peek() = " + stack.peek());
    //
    //System.out.println("stack.pop() = " + stack.pop());
    //
    //stack.display();
    //
    //Node<String> node1 = new Node<>("1");
    //node1.next = new Node<>("2");
    //node1.next.next = new Node<>("3");
    //node1.next.next.next = new Node<>("4");
    ////Node node = reverse2(node1);
    //
    //printListReversely(node1);

    int[] arr = { 8, 1, 18, 3, 5, 7, 9, 2, 4, 6, 11, 10 };
    /*int[] sort7 = */
    Sort.quickSort(arr, 0, arr.length - 1);
    System.out.println("sort7 = " + Arrays.toString(arr));
  }

  /**
   * 理解递归：输入一个数，输出i-0
   */
  private void fun(int i) {
    System.out.println("i = " + i);
    if (i > 0) {
      fun(--i);
    }
  }

  /**
   * 从尾到头输出单链表，采用递归方式实现
   */
  public void printListReversely(Node pListHead) {
    if (pListHead != null) {
      printListReversely(pListHead.next);
      System.out.println("printListReversely:" + pListHead.data);
    }
  }

  /**
   * 删除重复节点
   * 逐个遍历当前节点与后面所有节点值是否相等
   */
  public void deleteDuplecate(Node head) {
    Node temp = head;
    while (temp != null) {
      Node next = temp;
      while (next.next != null) {
        if (temp.data == next.next.data) {
          next.next = next.next.next;
        } else {
          next = next.next;
        }
      }
      temp = temp.next;
    }
  }

  /**
   * 排序
   */
  public Node orderList(Node<Integer> head) {
    Node<Integer> nextNode = null;
    int tmp = 0;
    Node<Integer> curNode = head;
    while (curNode.next != null) {
      nextNode = curNode.next;
      while (nextNode != null) {
        if (curNode.data > nextNode.data) {
          tmp = curNode.data;
          curNode.data = nextNode.data;
          nextNode.data = tmp;
        }
        nextNode = nextNode.next;
      }
      curNode = curNode.next;
    }
    return head;
  }

  public Node find(Node head, int k) {
    Node temp = head;
    for (int i = 0; i < 4 - k; i++) {
      temp = temp.getNext();
    }
    return temp;
  }

  /**
   * 查找倒数 第k个元素
   */
  public Node findElem(Node head, int k) {
    // 如果知道length 为什么不直接length()-k呢
    //if (k < 1 || k > this.length()) {
    //  return null;
    //}
    Node p1 = head;
    Node p2 = head;
    for (int i = 0; i < k; i++)// 前移k步
      p1 = p1.next;
    while (p1 != null) {
      p1 = p1.next;
      p2 = p2.next;
    }
    return p2;
  }

  /**
   * 递归反转链表，在反转当前节点之前先反转后续节点
   */
  public static Node reverse(Node head) {
    // head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
    if (head == null || head.getNext() == null) {
      return head;// 若为空链或者当前结点在尾结点，则直接还回
    }
    Node reHead = reverse(head.getNext());// 先反转后续节点head.getNext()
    head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
    head.setNext(null);// 前一结点的指针域令为null; // 这个目的是最后把尾节点置为null
    return reHead;// 反转后新链表的头结点
  }

  /**
   * 遍历，将当前节点的下一个节点缓存后更改当前节点指针
   */
  public static Node reverse2(Node head) {
    if (head == null) return head;
    Node pre = head;// 上一结点
    Node cur = head.getNext();// 当前结点
    Node tmp;// 临时结点，用于保存当前结点的指针域（即下一结点）
    while (cur != null) {// 当前结点为null，说明位于尾结点
      tmp = cur.getNext();
      cur.setNext(pre);// 反转指针域的指向

      // 指针往下移动
      pre = cur;
      cur = tmp;
    }
    // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
    head.setNext(null);

    return pre;
  }

  //判断单链表是否有环的方法
  public static boolean hasLoop(Node head) {
    Node p1 = head;    //定义一个引用指向头结点
    Node p2 = head.next;    //定义另一个引用指向头结点的下一个结点
    int circleIndex = 0;

    /**
     * 因为引用p2要比p1走的快，所以要用它作为循环的结束标志，为了防止当链表中个数为
     * 偶数时出现p2.next=null空指针异常，这时可以在循环中进行一下判断，如果这种情况
     * 出现一定是无环的。
     */
    while (p2 != null && p2.next != null) {
      circleIndex++;
      p1 = p1.next;
      p2 = p2.next.next;
      if (p2 == null) return false;
      if (p1.data == p2.data) return true;
    }
    return false;
  }
}
